package 左哥算法.ch07图;

import org.junit.Test;

import java.util.*;

public class Ch01遍历 {

    @Test
    public void test01(){
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        Node n4 = new Node(4);
        Node n5 = new Node(5);
        n1.nexts.add(n2);
        n1.nexts.add(n3);
        n1.nexts.add(n5);

        n2.nexts.add(n3);

        n3.nexts.add(n4);
        n3.nexts.add(n5);

        n5.nexts.add(n1);
        n5.nexts.add(n4);
//        n4.nexts.add(n3);
        System.out.print("宽度优先：");
        bfs(n1);
        System.out.println();
        System.out.print("深度优先(递归)：");
        dfsDigui(n1);
        System.out.println();
        System.out.print("深度优先(迭代)：");
        dfsDieDai(n1);
    }

    /**
     * 给你一个节点，要求你从该节点宽度优先遍历
     * 队列+hashSet思路：使用一个Set来防止循环遍历
     *      1.头节点初始化（入队和入set）
     *      2.依次对队列节点出队，将当前节点的邻居节点在Set中判断是否遍历过
     *          如果存在过：则跳至下一个邻居节点
     *          如果不存在则将该邻居节点入队入Set
     *      3.依次重复2，直到队列为空
     */
    public void bfs(Node root){
        Queue<Node> queue=new LinkedList<>();
        Set<Node> set=new HashSet<>();
        queue.add(root);
        set.add(root);
        while (!queue.isEmpty()){
            Node node = queue.poll();
            System.out.print(node.val+" ");
            for (Node next : node.nexts) {
                if (!set.contains(next)){
                    queue.add(next);
                    set.add(next);
                }
            }
        }
    }

    /**
     * 前序深度优先遍历
     *栈+set的思路：
     *      1.对头初始化（入栈，入set）
     *      2.对节点进行出栈，对该节点的子节点进行入栈（如果不存在于set中）
     *      3.重复2
     */
    Set<Node> set=new HashSet<>();
    public void dfsDigui(Node node){
        if (node==null){
            return;
        }
        set.add(node);
        System.out.print(node.val+" ");
        for (Node next : node.nexts) {
            if (!set.contains(next)){
                dfsDigui(next);
            }
        }
    }

    /**
     * 前序深度优先
     */
    public void dfsDieDai(Node root){
        Set<Node> set=new HashSet<>();
        Stack<Node> stack=new Stack<>();
        set.add(root);
        stack.push(root);
        while (!stack.isEmpty()) {
            Node node = stack.pop();
            System.out.print(node.val+" ");
            for (int i =node.nexts.size()-1; i>=0; i--) {   //前序要倒着入栈
                if (!set.contains(node.nexts.get(i))){
                    stack.add(node.nexts.get(i));
                    set.add(node.nexts.get(i));
                }
            }
//            for (Node next : node.nexts) {
//                if (!set.contains(next)){
//                    set.add(next);
//                    stack.push(next);
//                }
//            }
        }
        return;
    }
}
